﻿// Copyright (c) 2011 Dan Popick

// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:

// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.

// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

using Open.Web.Stijl;

namespace Open.Web.Stijl.Partitioning
{
	/// <summary>
	/// Partitions items into a group of sets, ideally optimal.
	/// </summary>
	/// <typeparam name="T"></typeparam>
	/// <remarks>
	/// Notes: 
	/// 
	/// For some reason, the partitioning seems to create additional groups when it should 
	/// probably stick with assigning elements to existing groups. Evaluating the alternatives
	/// seems to find better solutions
	/// </remarks>
	public class RepeatingPartitioner<T> where T : PartitionedItem
	{
		static Utility.Tracer<RepeatingPartitioner<T>> _log = new Utility.Tracer<RepeatingPartitioner<T>>();
		static Configuration.StijlConfiguration _config = Configuration.StijlConfiguration.Default;

		class PotentialStep
		{
			public T Item { get; set; }
			public int SetIndex { get; set; }
			public int Size { get { return Factors.Size; } }
			public int Overlap { get; set; }
			public int Cost { get; set; }
			public FactorSet Factors { get; set; }

			public PotentialStep() { }
			public PotentialStep(T item, Set<T> set)
			{
				Item = item;
				SetIndex = set.Index;
				
				ComputeCost(set);
			}

			/// <summary>
			/// Computes the cost based on the increased area of the existing image + the increase of the additional image
			/// </summary>
			/// <remarks>
			/// That is:
			/// 
			/// XXXX          YYY
			/// XXXX   and    YYY
			/// XXXX
			/// 
			/// yields
			/// 
			/// XXXX........
			/// XXXX........
			/// XXXX........
			/// YYY.........
			/// YYY.........
			/// 
			/// (X - Y = 3) * (X.Height = 3) + (Y - X = 4) * (Y.Height = 2) = 17
			/// </remarks>
			void ComputeCost(Set<T> set)
			{
				FactorSet diff = set - Item;
				Overlap = diff.Size;
				Factors = set + Item;

				if (set.Count == 0)
					Cost = _config.TiledImageThreshold; 
				else
				{
					FactorSet diff2 = Item - set;

					Cost = ((diff.Size == 1 ? 0 : diff.Size) * set.Size * set.SecondarySize)
						+ ((diff2.Size == 1 ? 0 : diff2.Size) * Item.Size * Item.SecondarySize);
				}
			}
		}

		class Artefacts
		{
			public List<PotentialStep> Steps;
		}

		public PartialSolution<T> FindSolution(List<T> unassigned)
		{
			PartialSolution<T> initial = new PartialSolution<T>();
			List<PartialSolution<T>> potentialSet = new List<PartialSolution<T>>();
			List<PartialSolution<T>> solutionSet = new List<PartialSolution<T>>();
			List<T> nonFactoredItems = new List<T>();
			List<T> orderedItems = new List<T>();

			// split into usable/unusable items, assign unusable items after finding the solution
			nonFactoredItems.AddRange(unassigned.Where(x => !x.IsFactorizable));
			initial.Unassigned = unassigned.Where(x => x.IsFactorizable).ToList();

			solutionSet.Add(Solve(initial, potentialSet, orderedItems));

			int i = _config.RepeatingSolutionLimit;
			while (potentialSet.Count > 0 && i > 0)
			{
				--i;

				// find the step with the minimum cost
				PartialSolution<T> alternative = potentialSet.MinElement(x => ((Artefacts)x.Artefacts).Steps.First().Cost);
				Artefacts facts = (Artefacts)alternative.Artefacts;
				PotentialStep step = facts.Steps[0];

				if (_log.IsDebugEnabled)
					_log.Debug("-------------------- alternative solution ---------------------\r\n{0}", alternative.Log());

				// if any potential steps remain remove the min step otherwise remove the partial solution from the set
				PartialSolution<T> workingAlt;
				if (facts.Steps.Count > 1)
				{
					facts.Steps.RemoveAt(0);
					workingAlt = new PartialSolution<T>(alternative);
				} else {
					// no need to copy the 'alternative' here since we're removing it from the partial solution set
					workingAlt = alternative; 
					potentialSet.Remove(alternative);
				}

				workingAlt.Unassigned.Remove(step.Item);

				// Assign the selected item to the selected set, accounting for the new item
				// TODO: this (and other) logic would be a lot more simple if we ensure that AssignedGroups will always
				// contain an empty set.
				if (workingAlt.AssignedGroups.Count == step.SetIndex)
				{
					Set<T> newSet = new Set<T>(workingAlt.AssignedGroups.Count);
					newSet.Add(step.Item);
					workingAlt.AssignedGroups.Add(newSet);
					_log.Debug("  assigning {0} to a new set, #{1}", step.Size, step.SetIndex);
				}
				else
				{
					workingAlt.AssignedGroups[step.SetIndex].Add(step.Item);
					_log.Debug("  assigning {0} to set #{1}", step.Size, step.SetIndex);
				}
				workingAlt.Level = workingAlt.Level + 1;

				// solve the rest
				solutionSet.Add(Solve(workingAlt, potentialSet, orderedItems));

				// For n unassigned elements, the maximum number of potential steps is (n / 2)^2, and the
				// branched solutions < n*((n / 2) ^ 2) = c•n^3, definitely not a viable memory profile
				// so we trim the excess here (we'll never care about more solutions than the solution limit)
				if (potentialSet.Count > _config.RepeatingSolutionLimit) // TODO: tune
					potentialSet.RemoveRange(_config.RepeatingSolutionLimit, potentialSet.Count - _config.RepeatingSolutionLimit);
			}

			if (_log.IsDebugEnabled)
			{
				solutionSet.Sort((x, y) => x.GetTotalArea() - y.GetTotalArea());
				_log.Debug(" **************************** Final Ordered Solutions **************************** ");
				for (int ij = 0; ij < solutionSet.Count; ++ij)
				{
					_log.Debug("Cost: {0}\r\n{1}", solutionSet[ij].GetTotalArea(), solutionSet[ij].Log());
				}
			}

			// TODO: should maybe be a Sort((x,y) => func).First(), to do a more nuanced comparison than the area-based
			// one
			PartialSolution<T> finalSoluton = solutionSet.MinElement(x => x.GetTotalArea());
			finalSoluton.AssignedGroups.AddRange(
				from nonFactored in nonFactoredItems
				select Set<T>.FromItem(0, nonFactored));

			return finalSoluton;
		}

		static PartialSolution<T> Solve(PartialSolution<T> initial, List<PartialSolution<T>> potentialSet, List<T> orderedItems)
		{
			PartialSolution<T> activeSol = initial;
			int level = activeSol.Level;

			while (activeSol.Unassigned.Count > 0)
			{
				Set<T> s = new Set<T>(activeSol.AssignedGroups.Count);
				IEnumerable<PotentialStep> potentials;

				if (level < orderedItems.Count)
				{
					// if we already have selected the item for this level, only consider 
					// possibilities for placement of that item
					T item = orderedItems[level];
					potentials = from set in activeSol.AssignedGroups.Union(s)
								 let potential = new PotentialStep(item, set)
								 orderby potential.Cost ascending
								 select potential;
				} else
					// if this is the first time through this level, consider all unassigned items
					potentials = from item in activeSol.Unassigned
								 from set in activeSol.AssignedGroups.Union(s)
								 let potential = new PotentialStep(item, set)
								 orderby potential.Cost ascending
								 select potential;

				Artefacts facts = new Artefacts();
				facts.Steps = potentials.ToList();
				PotentialStep ps = facts.Steps[0];

				// only retain steps which relate to the selected item
				facts.Steps.RemoveAll(x => x.Item != ps.Item);

				// TODO: re-evaluate this removal; some moves may pay out farther into the analysis
				facts.Steps.RemoveAll(x => x.Cost > (_config.TiledImageThreshold * 2)|| x.Item != ps.Item);

				// if there is more than one alternative, add this to the solution stack
				if (facts.Steps.Count > 1)
				{
					facts.Steps.RemoveAt(0);

					PartialSolution<T> currentSolution = new PartialSolution<T>(activeSol);
					currentSolution.Artefacts = facts;

					potentialSet.Add(currentSolution);
				} 

				// Assign the selected item to the selected set, accounting for the new item
				// TODO: this (and other) logic would be a lot more simple if we ensure that AssignedGroups will always
				// contain an empty set.
				if (activeSol.AssignedGroups.Count == ps.SetIndex)
				{
					Set<T> newSet = new Set<T>(activeSol.AssignedGroups.Count);
					newSet.Add(ps.Item);
					activeSol.AssignedGroups.Add(newSet);
					_log.Debug("  assigning {0} to a new set, #{1}", ps.Item.Size, newSet.Index);
				}
				else
				{
					activeSol.AssignedGroups[ps.SetIndex].Add(ps.Item);
					_log.Debug("  assigning {0} to set #{1}", ps.Item.Size, ps.SetIndex);
				}

				activeSol.Unassigned.Remove(ps.Item);
				activeSol.Level = ++level;
			}

			return activeSol;
		}
	}
}
